APIO2020练习赛 B题题解

首先祝各位：APIO & NOI RP++!

题目来源：APIO2020练习赛 B （我不知道大家能不能看到这个链接的题目）

题目翻译

• 这是一道交互题。
• 有一张二分图，左侧有$N$个点，右侧有$M$个点。保证$N\neq M$。
• 你可以向交互库提出如下询问：给定一个点集$S$，交互库会返回与$S$中任意点相邻的所有点。
• 你需要通过至多$Q$次询问，找到一个度数不为$1$的点。由于$N\neq M$，一定存在这样的点。

数据范围：$1\le N,M\le 50,\ Q=7,\ N\neq M$。

一道很考察思维和代码细节的题。（反正我被坑了很久）

首先看数据范围，发现$Q=7$，大概可以猜到需要$O(\log (N+M))$次查询的算法才能通过。（也可以联想到$7^2=49=50-1$，不过和此题好像没啥联系）

分析这个交互过程：现在假设你询问了一个同属一侧的点集$A$，返回的结果是$B$。那么：

• 对于任意$x\in B$都存在一个$y\in A$满足$x,y$相邻。
• 对于任意$x\notin B$都不存在一个$y\in A$满足$x,y$相邻。

乍一看这两句话是废话，就是把询问的方式重新说了一遍。不过我们可以找到一些很好的性质，如果我们现在再查询一下$B$呢？假设返回的集合是$C$。那么：

• 如果有一个点$x\in A,x\notin C$。可以断定$x$的度数一定为$0$，否则如果它和$y$相连，一定有$y\in B$，那么必然$x\in C$，矛盾。
• 如果有一个点$x\notin A,x\in C$。一定存在一个$y\in B$且$x,y$相连，然后一定存在一个$z\in A$且$y,z$相连。又因为$x\notin A,z\in A$，$x\neq z$。那么$y$同时与$x,z$相连，度数至少为$2$。
• 换句话说，只要此时$A\neq C$，那么我们找到了一个度数不为$1$的点。

如果我们没找到即$A=C$，那这个二分图中所有的边要么在$A∪B$里，要么在$A∪B$外。这两部分是不连通的，可以递归处理。我们找到这两部分中满足两侧点数不相等且较小的一部分，递归下去。如果我们选取的$A$适当，每次就可以把问题的大小减半，这样就能做到$O(\log)$次查询了。

然而这么做的查询次数大概是$2\log$，并不能过题……考虑优化一下。显然你可以选定一个左点集的子集和右点集的子集，把他们放到一起询问，然后你还能很方便地分开交互库返回的结果。然后发现，之前的分析中$B→C$的询问和递归后$A→B$的询问可以合并起来。然后你就糊出了一个复杂度正确但是非常鬼畜的做法。